package Algorithm.interview;

/**
 * @Author self
 * @Date 2024/9/13 21:28
 * @Describe 二叉树的最大路径和问题是一个经典的动态规划和递归问题，
 * 目的是找到二叉树中任意两个节点之间的路径，且路径和最大。
 * 路径可以从任意节点开始和结束，但必须沿父子节点的方向走。
 *
 * 这个问题的解法可以使用递归的方式，通过后序遍历来计算每个节点的最大贡献值（从该节点向下的最大路径和），并在计算过程中更新全局的最大路径和。
 *
 * 解题思路：
 * 对于每个节点，计算以该节点为终点的最大路径和（只能从左子节点或右子节点单向到该节点）。
 * 更新全局的最大路径和：对每个节点，可能的最大路径和是该节点的值加上其左子树和右子树的最大路径和（如果为正值的话）。
 * 使用递归来遍历每个节点，计算它的最大贡献值，同时更新全局的最大路径和。
 */


public class MaxSum {
    // 定义一个全局变量来记录最大路径和
    private int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        // 调用递归函数计算最大路径和
        calculateMaxPath(root);
        return maxSum;
    }

    // 递归计算以当前节点为终点的最大路径和
    private int calculateMaxPath(TreeNode node) {
        if (node == null) {
            return 0;  // 空节点的贡献值为0
        }

        // 递归计算左右子树的最大路径和，负数的话我们直接舍弃
        int leftMax = Math.max(0, calculateMaxPath(node.left));   // 左子树的最大贡献值
        int rightMax = Math.max(0, calculateMaxPath(node.right)); // 右子树的最大贡献值

        // 更新最大路径和：当前节点的值 + 左子树最大贡献 + 右子树最大贡献
        int currentMax = node.val + leftMax + rightMax;
        maxSum = Math.max(maxSum, currentMax);

        // 返回当前节点的最大贡献值，只能选左子树或者右子树
        return node.val + Math.max(leftMax, rightMax);
    }

    public static void main(String[] args) {
        // 创建二叉树
        TreeNode root = new TreeNode(-10);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        // 计算最大路径和
        MaxSum solution = new MaxSum();
        int result = solution.maxPathSum(root);
        System.out.println("最大路径和是: " + result);  // 输出最大路径和
    }
}

